Low Density Parity Check (LDPC) Codes (Part 1)

In this post, we explore the low-density parity check (LDPC) code in the 5G standard. The LDPC code is a linear block code with a sparse parity-check matrix, which is also called an LDPC matrix. The LDPC matrix is denoted by \(H\in\{0,1\}^{n-k,k}\), where the number of 1s \(\ll n(n-k)\).

1. Review of Parity Check Codes

Consider an example of the parity-check matrix

\[ H = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{bmatrix} \]

The codeword should satisfy \[ c = [c_1, ..., c_7], \] where \(Hc^\mathrm{T}=0\)

2. Tanner Graph

The parity check code can be represented by Tanner graph - Bit nodes <-> Columns - Check nodes <-> Rows - Edges <-> 1s - Degree of bit nodes <-> Weight of column - Degree of check node <-> weight of row

image.png

3. LDPC codes in standards

3.1. General Instruction

  • Photograph construction of LDPC codes in standards
    • Base graphs for different rates
    • Expanded by right shift permutation matrices
    • Optimised for performance vs complexity
  • 5G-NR
    • Two base graphs (BG1: 46x68, BG2: 42x52)
    • Block structure of base matrices \[ \begin{bmatrix} A & E & O \\ B & C & I \end{bmatrix} \]
    • BG1:
      • A: 4 x 22, E: 4 x 4, O: 4 x 42 all zero
      • B: 42 x 22, C: 42 x 4, I: 42 x 42 identity
    • BG2:
      • A: 4 x 10, E: 4 x 4, O: 4 x 38 all zero
      • B: 38 x 10, C: 38 x 4, I: 38 x 38 identity
    • Several expansions
    • Shortening and puncturing for multiple rates.

Example)

\[ B = \begin{bmatrix} 1 & -1 & 3 & 1 & 0 & -1 \\ 2 & 0 & -1 & 0 & 0 & 0 \\ -1 & 4 & 2 & 1 & -1 & 0 \end{bmatrix} \]

Expansion factor: 5 [-1, 0, 1, 2, 3, 4] - -1: all zeros - 0~4: right-shift permuation of identity matrix

image.png

Example 2: BG2)

image-2.png

3.2. Expansion factor \(Z_c\)

  • Index and expansion factors
    • iLs: 0, 1, 2, 3, 4, 5, 6, 7
    • a: 2, 3, 5, 7, 9, 11, 13, 15
    • \(J_a\): 7, 7, 6, 5, 5, 5, 4, 4
    • \(Z_c\): \(a\times 2^j\), \(j=0,1,2,...,j_a\)
      • Max Zc = 384
  • For each Zc, base matrix entries specified
    • -1, 0, 1, …, \(Z_c\) -1.
    • -1: Zc x Zc all-zero matrx
    • 0 to Zc-1: identity shifted right i times.

image.png